package toOffer

/*
	给你一个字符串 s，找到 s 中最长的回文子串。

	示例 1：

	输入：s = "babad"
	输出："bab"
	解释："aba" 同样是符合题意的答案。
	示例 2：

	输入：s = "cbbd"
	输出："bb"
	示例 3：

	输入：s = "a"
	输出："a"
	示例 4：

	输入：s = "ac"
	输出："a"

	提示：

	1 <= s.length <= 1000
	s 仅由数字和英文字母（大写和/或小写）组成

	来源：力扣（LeetCode）
	链接：https://leetcode-cn.com/problems/longest-palindromic-substring
	著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处
*/

func longestPalindrome(s string) string {
	dp := make([][]bool, len(s)) // dp[i][j]表示[i...j]范围内的字符串是否是回文串
	for i := 0; i < len(dp); i++ {
		dp[i] = make([]bool, len(s))
	}
	longestSubStr := ""
	for i := len(dp) - 1; i >= 0; i-- {
		for j := i; j < len(dp); j++ {
			if i == j {
				dp[i][j] = true
			} else if i+1 == j {
				dp[i][j] = s[i] == s[j]
			} else {
				dp[i][j] = dp[i+1][j-1]&&(s[i]==s[j])
			}
			if dp[i][j] {
				longestSubStr = max(longestSubStr, s[i:j+1])
			}
		}
	}
	return longestSubStr
}

func max(a string, b string) string {
	if len(a)>len(b) {
		return a
	}
	return b
}
